/**
 * @author 徐楠
 * @date 2022/3/27 20:22
 * @version 1.0
 */

package com.xunan.likou;

public class WarshipOnDeck {
    public static void main(String[] args) {
        char board[][] = {{'X','.','.','X'}, {'.','.','.','X'},{'.','.','.','X'}};
        int result = countBattleships1(board);
        System.out.println(result);
    }

    /**
     * 题意是说，X是战舰，X的长度位置，X的放置方向未知，可以是横着，可以是竖着
     * 大家可以理解一张白纸（矩阵）
     * 画着一堆数字1，而1可能是横着的，也可能是竖着的，并且1的长度是未知的，1则是由X组成的
     * 比如
     * XXXXXX 是一个战舰
     *
     * X
     * X
     * X
     * X
     * 是一个战舰
     *
     * X是一个战舰
     *
     * XX也是一个战舰
     *
     * 咱们的目的是统计战舰的个数，
     * 并且题目保证不会出现这样的情况
     * XXX
     * X
     *
     * XXX
     * X
     * X
     *
     * 只会出现单独的一条线的 XXX，或者横着，或者竖着。
     *
     */

    /**
     *
     * 思考上述两种做法，我们本质 都是在战舰的首个格子进行计数，并将该战舰的所有格子进行处理，
     * 同时使用去重手段（原数组标记 或 使用辅助数组）来防止该战舰在后面遍历中被重复计数。
     *
     * 如果我们能够找到某种规律，直接判断出某个 X 格子是否为战舰开头，则不再需要其他去重手段。
     *
     * 当且仅当某个 X 格子的「上方」&「左方」不为 X 时，该格子为战舰首个格子，可以进行计数，
     * 同时需要注意当前当为 00（没有「上方」）和当前列为 00（没有「左方」）时的边界情况。
     *
     *
     */
    public static int countBattleships1(char[][] board) {
        int m = board.length, n = board[0].length;
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && board[i - 1][j] == 'X') continue;
                if (j > 0 && board[i][j - 1] == 'X') continue;
                if (board[i][j] == 'X') ans++;
            }
        }
        return ans;
    }

    /**
     * 解题方法：
     * 用ans记录战舰的个数
     * 遇见一个X，我们需要考虑它是横着的一部分还是竖着的一部分
     * 我们先ans++;
     * 1.如果它是竖着的一部分，我们直接看(i-1,j)这个坐标，如果也是'X',那么ans--，因为一定是上一行已经统计过的了。
     * 2.如果它是横着的一部分，我们看(i,j-1)这个坐标，如果也是'X',那么 ans--，因为一定是这一行前一列已经统计过的了。
     * 综上，也就是说，只有当这个点是一个战舰的头部的时候，我们才会记录到ans中。
     *
     */
    public static int countBattleships2(char[][] board) {
        int ans=0;
        int n=board.length;
        int m=board[0].length;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(board[i][j]=='X'){
                    ans++;
                    if(i>0&&board[i-1][j]=='X') ans--;
                    if(j>0&&board[i][j-1]=='X') ans--;
                }
            }
        }
        return ans;
    }


}
